#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 376. 摆动序列
    // https://leetcode.cn/problems/wiggle-subsequence/
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n, 1);
        auto g = f;

        for (int i = 1; i<n; ++i)
        {
            for (int j = 0; j<i; ++j)
            {
                if (nums[j] > nums[i])
                    g[i] = max(f[j]+1, g[i]);
                if (nums[j] < nums[i])
                    f[i] = max(g[j]+1, f[i]);
            }
        }

        return max(g[n-1], f[n-1]);
    }

    // 673. 最长递增子序列的个数
    // https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1);
        auto count = len;

        int maxlen = 1;
        int ans = 0;

        for (int i = 1; i<n; ++i)
        {
            for (int j = 0; j<i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    if (len[j] + 1 == len[i])
                        count[i] += count[j];
                    else if (len[j] + 1 > len[i])
                    {
                        count[i] = count[j];
                        len[i] = len[j] + 1;
                    }
                }
            }
            maxlen = max(maxlen, len[i]);
        }

        for (int i = 0; i<n; ++i)
        {
            if (len[i] == maxlen)
                ans += count[i];
        }

        return ans;
    }

    // 646. 最长数对链
    // https://leetcode.cn/problems/maximum-length-of-pair-chain/
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        vector<int> len(n, 1);
        sort(pairs.begin(), pairs.end());

        int maxlen = 1;

        for (int i = 1; i<n; ++i)
        {
            for (int j = 0; j<i; ++j)
            {
                if (pairs[j][1] < pairs[i][0])
                    len[i] = max(len[j]+1, len[i]);
            }
            maxlen = max(maxlen, len[i]);
        }

        return maxlen;
    }
};